package lz;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.Stack;

/**
 * 数组和树的转换
 * @param <T>
 */
public class ArrayWithTree<T> {
    /**
     * 数组转化成树
     * @param arr
     * @param index
     * @return
     */
    public Node<T> convert(int[] arr, int index) {
        if(index >= arr.length) {
            return null;
        }
        Node<T> node = new Node(arr[index]);
        node.left = convert(arr, 2*index + 1);
        node.right = convert(arr, 2* index + 2);
        return node;
    }

    /**
     * 树转化成数组
     * @param root
     */
    public int[] treeToArray(Node<T> root) {
        int height = getHeight(root);
        int length = (int) Math.pow(2, height) - 1;
        int[] array = new int[length];
        convertToArray(array, root, 0);
        return array;
    }

    private void convertToArray(int[] array, Node<T> root, int index) {
        if (root == null) {
            return;
        }
        array[index] = (Integer) root.data;
        convertToArray(array, root.left, 2 * index + 1);
        convertToArray(array, root.right, 2 * index + 2);
    }

    /**获取树的高度
     * @param root
     * @return
     */
    private int getHeight(Node<T> root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    }

    public void preHeadTraversal(Node<T> root) {
        if(null == root) {
            return;
        }
        System.out.print(root.data + " ");
        preHeadTraversal(root.left);
        preHeadTraversal(root.right);
    }

    public void middleHeadTraversal(Node<T> root) {
        if(null == root) {
            return;
        }
        middleHeadTraversal(root.left);
        System.out.print(root.data + " ");
        middleHeadTraversal(root.right);
    }

    public void postHeadTraversal(Node<T> root) {
        if( null == root) {
            return;
        }
        postHeadTraversal(root.left);
        postHeadTraversal(root.right);
        System.out.print(root.data + " ");
    }

    public void output(Node<T> root) {
        if(null == root) {
            return;
        }
        Queue<Node<T>> queue = new ArrayDeque<>();
        queue.add(root);

        while(!queue.isEmpty()) {
            Node<T> node = queue.poll();
            System.out.print(node.data + " ");
            if(null != node.left) {
                queue.add(node.left);
            }
            if(null != node.right) {
                queue.add(node.right);
            }
        }
    }

    public void postorderTraversal(Node<T> root) {
        if (root == null) return;

        Stack<Node<T>> stack = new Stack<>();
        Stack<Node<T>> output = new Stack<>(); // 用于反转访问顺序
        stack.push(root);

        while (!stack.isEmpty()) {
            Node<T> node = stack.pop();
            output.push(node); // 先访问的节点后输出

            // 左子树先入栈（后访问）
            if (node.left != null) {
                stack.push(node.left);
            }
            // 右子树后入栈（先访问）
            if (node.right != null) {
                stack.push(node.right);
            }
        }

        // 输出结果（后序遍历顺序）
        while (!output.isEmpty()) {
            System.out.print(output.pop().data + " ");
        }
    }


    public Node<T> test() {
        int[] arr = new int[] {1,2,3,4,5,6,7};
        Node<T> root = convert(arr, 0);
        return root;
    }

    public static void main(String[] args) {
        ArrayWithTree t = new ArrayWithTree();
        Node node = t.test();

        int[] array = t.treeToArray(node);
        Arrays.stream(array).forEach(System.out::println);

//        t.output(node);
//        System.out.println();
//        t.preHeadTraversal(node);
//        System.out.println();
//        t.middleHeadTraversal(node);
//        System.out.println();
//        t.postHeadTraversal(node);
//        System.out.println();
//        t.postorderTraversal(node);

    }

    private static class Node<E> {
        E data;
        private Node<E> left;
        private Node<E> right;

        public Node(E data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }
}